package solution;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-19
 * Time: 19:52
 */


//https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=188&&tqId=38575&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class Solution8 {
    //使用队列的性质,只遍历一边
    public int FirstNotRepeatingChar(String str) {
        Map<Character, Integer> map = new HashMap<>();
        Deque<Character> q1 = new LinkedList<>();
        Deque<Integer> q2 = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            if (!map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), i);
                q1.offer(str.charAt(i));
                q2.offer(i);
            } else {
                map.put(str.charAt(i), -1);
                while (!q1.isEmpty() && map.get(q1.peek()) == -1) {
                    q1.poll();
                    q2.poll();
                }
            }
        }
        return q2.isEmpty() ? -1 : q2.peek();
    }
}
